In digital communications systems, received data may have been corrupted by noise and distortion. As such, digital data obtained at the receiving station may not be an accurate replica of the data transmitted. Such errors may be reduced by encoding the transmitted data to add redundancy to the data before transmission.
Redundancy may be introduced by increasing the symbol rate. For example, error checking and error correcting codes may be appended to fixed-length blocks of source data and the combination then sent at a higher data rate. The resulting increase in bandwidth, however, subjects the receiver to additional noise.
As an alternative, signal-space codes may be utilized to add redundancy by converting the source data into a "line code" which may be sent at the same symbol rate but which utilizes an enlarged number of possible symbols (discrete points within the signal space). The bandwidth required by such codes is no larger than that of an equivalent encoded system, such that there is no increase in noise at the receiver. However, due to the fact that symbols must be more closely spaced to avoid an increase in transmitted power, noise immunity is reduced. In transmission systems having a limited, fixed bandwidth, such as a voice-grade telephone link, signal-spaced coding permits significantly higher rates of error-corrected transmission to be realized.
One class of signal-spaced code which has seen increasing acceptance due to its superior performance is the "trellis code," a convolutional code best explained utilizing a trellis diagram. In the trellis diagram, vertical columns of nodes represent the possible states which can be assumed at successive points in time by a "state machine" which encodes the source data. Before transmission begins, the encoding machine is initialized to a predetermined state. Thereafter, each transmitted symbol specifies the transition from the current state to a limited number of permissible successor states. The sequence of symbols previously transmitted specifies the current state of the encoding machine. The current state in turn specifies which symbols out of the entire alphabet may validly appear next in the transmitted sequence. Thus, only selected sequences of transmitted symbols are permitted by the coding scheme and these legitimate sequences may be represented by paths through the trellis diagram.
Each transmitted symbol accordingly represents not only a source code, but also contains historical information, reflected in the state information which can be derived from the received sequence of symbols. This redundancy permits the transmitted symbol sequence to be accurately reconstructed in a decoding operation even though noise and distortion have altered the message-bearing signal during transmission.
Trellis coding is utilized to particular advantage in the implementation of voice band data modems of the type used to provide high, error-free data rates over dial-up and leased line analog telephone facilities. In order to process these structures, the highly efficient Viterbi algorithm has been utilized, named after its originator, A. J. Viterbi. The Viterbi technique makes use of the fact that a number of the transitions to a given state can be deleted, as they do not represent the least-likely path to that transition. In this matter, a lower number of transitions is required to be stored when determining the most likely path between states.